package algorithmTopics.tree;

import java.util.*;
import java.util.stream.Collectors;


class Solution {


    private int ans1 = Integer.MIN_VALUE;

    /**
     * 最大路径总和
     *
     * @param root 根节点
     * @return int 最大和的值
     */
    public int maxPathSum(TreeNode root) {
        dfsH(root);
        return ans1;
    }
    private int dfsH(TreeNode node){
        if(node == null){
            return 0;
        }
        // 左右 字串的长度
        int L = dfs(node.left);
        int R = dfs(node.right);
        //当前拼起来是否是最大的
        ans1 = Math.max(ans1 , L + R + node.val);
        // 看看当前节点作为子串 是不是大于0，
        return Math.max(Math.max(L,R)+node.val,0);
    }

    /**
     * q p 的最低共同祖先
     *
     * @param root 根节点
     * @param p    p
     * @param q    q
     * @return 祖先节点
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        return root;
    }


    /**
     * 路径总和 等于目标值
     *
     * @param root      根
     * @param targetSum 目标金额
     * @return int 符合条件的路径数量
     */
    private List<List<Long>> sums = new ArrayList<>();
    public int pathSum(TreeNode root, int targetSum) {
        if(root == null){ return 0;}
        // 当前节点 和他父节点的 sum 的所有情况
        sums.add(List.of((long)root.val));
        pathSumHelper(root.left, List.of((long)root.val));
        pathSumHelper(root.right, List.of((long)root.val));
        int res = 0;
        for (int i = 0; i < sums.size(); i++) {
            for (int j = 0; j < sums.get(i).size(); j++) {
                if (sums.get(i).get(j) == targetSum) {
                    res++;
                }
            }
        }
        return res;
    }

    private void pathSumHelper(TreeNode root, List<Long> list) {
        //
        if (root == null) {
            return;
        }
        List<Long> collect = list.stream().map(a -> a + root.val).collect(Collectors.toList());
        collect.add((long) root.val);
        sums.add(collect);
        pathSumHelper(root.left,collect);
        pathSumHelper(root.right,collect);
    }

    /**
     * 构建树
     *
     * @param preorder 预购
     * @param inorder  inorder
     * @return {@link TreeNode}
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // inorder 存储到map方便获取 index
        HashMap<Integer, Integer> mapInorder = new HashMap<>();
        int length = inorder.length;
        for (int i = 0; i < length; i++) {
            mapInorder.put(inorder[i],i);
        }
        //根节点
        TreeNode root = new TreeNode(preorder[0]);
        for (int i = 1; i < length; i++) {
            TreeNode curr = root;
            //当前树的值
            int num = preorder[i];
            //需要知道放在哪个位置
            for (int j = 0; j < i; j++) {
                if (getDir(mapInorder, num, curr.val) == 1) {
                    // 右边
                    if (curr.right != null) {
                        curr = curr.right;
                        continue;
                    }
                    curr.right = new TreeNode(num);
                } else {
                    if (curr.left != null) {
                        curr = curr.left;
                        continue;
                    }
                    curr.left = new TreeNode(num);
                }
                break;
            }

        }

        return root;
    }

    /**
     * 获取dir
     *
     * @param mapInorder 顺序映射
     * @param num        num 需要插入到二叉树的值
     * @param target     目标
     * @return int 1 是右边 ，-1 左边
     */
    private int getDir( HashMap<Integer, Integer> mapInorder,int num , int target){
        int[] ints = {-1, 1};
        return ints[0] = mapInorder.get(num) > mapInorder.get(target) ? ints[1] : ints[0];
    }


    /**
     * 展开 二叉树 为单项链表形式 升序
     *
     * @param root 根
     */
    public void flatten(TreeNode root) {
       preOrderFlatten(root);
    }

    private TreeNode preOrderFlatten(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode right = root.right;
        // 先把左边展开
        if (root.left != null) {
            TreeNode currLeft = preOrderFlatten(root.left);
            root.left = null;
            root.right = currLeft;
            //右边展开
            TreeNode currRight = preOrderFlatten(right);
            while (currLeft.right != null) {
                currLeft = currLeft.right;
            }
            currLeft.right = currRight;
        }
        if (root.right != null) {
            preOrderFlatten(root.right);
        }


        return root;
    }

    /**
     * 右侧视图
     *
     * @param root 根
     * @return {@link List}<{@link Integer}>
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        rightSideViewHelper(root,res,0);
        return res;
    }

    private void rightSideViewHelper(TreeNode root, List<Integer> res , int depth) {
        if (root == null) {
            return;
        }
        if (depth == res.size()) {
            res.add(root.val);
        }
        rightSideViewHelper(root.right,res,depth + 1);
        rightSideViewHelper(root.left,res,depth + 1);

    }

    /**
     * BFS 中第K 个 最小
     *
     * @param root 根
     * @param k    k
     * @return int
     */
    public int kthSmallest(TreeNode root, int k) {
        int res = root.val;
        //kthSmallestHelper(root , res , k);
        return res;
    }



    /**
     * 是有效 二叉搜索树
     *
     * @param root 根
     * @return boolean
     */
    public boolean isValidBST(TreeNode root) {
        // 方法二
        // 直接遍历，记录当前的最小和最大值
        return isBSTHelper(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }

    private boolean isBSTHelper(TreeNode root, long min, long max) {
        if (root == null) {
            return true;
        }
        long x = root.val;
        return min < x && x < max && isBSTHelper(root.left,min,x) && isBSTHelper(root.right,x,max);
    }
//        // 转化为 升序数组 中序遍历
//        ArrayList<Integer> list = new ArrayList<>();
//        isBSTHelper(root,list);
//        for (int i = 0; i < list.size() - 1; i++) {
//            if (list.get(i) > list.get(i + 1)) {
//                return false;
//            }
//        }
//        return true;
//    }
//
//    private void isBSTHelper(TreeNode root, List<Integer> list) {
//        if (root == null) {
//            return;
//        }
//        isBSTHelper(root.left,list);
//        list.add(root.val);
//        isBSTHelper(root.right,list);
//    }
    /**
     * 已排序数组 -> 平衡二叉树
     *
     * @param nums nums
     * @return {@link TreeNode}
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums,0,nums.length - 1);
    }

    private TreeNode helper(int[] nums, int left , int right) {
        if (left > right) {
            return null;
        }
        int mid = (left + right) / 2;
        return new TreeNode(nums[mid],helper(nums,left,mid - 1),helper(nums,mid + 1,right));

    }


    /**
     * 输出层序排列的数组
     *
     * @param root 根
     * @return {@link List}<{@link List}<{@link Integer}>>
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        // 方法二 队列
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if (root != null) {
            queue.add(root);
        }
        while (!queue.isEmpty()) {
            //存储每一层的结果
            ArrayList<Integer> temp = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                temp.add(poll.val);
                if (poll.left != null) {
                    queue.add(poll.left);
                }
                if (poll.right != null) {
                    queue.add(poll.right);
                }
            }
            res.add(temp);

        }

        return res;
    }
   /* Map<Integer, List<Integer>> listMap = new HashMap<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        levelOrderHelper(root, 0);
        for (int i = 0; i < listMap.size(); i++) {
            res.add(listMap.get(i));
        }
        return res;
    }

    private void levelOrderHelper(TreeNode root , int depth) {
        if (root == null) {
            return ;
        }
        listMap.merge(depth, new ArrayList<>(List.of(root.val)), new BiFunction<List<Integer>, List<Integer>, List<Integer>>() {
            @Override
            public List<Integer> apply(List<Integer> integers, List<Integer> integers2) {
                integers.add(integers2.get(0));
                return integers;
            }
        });
        levelOrderHelper(root.left,depth + 1);
        levelOrderHelper(root.right,depth + 1);
    }*/


    /**
     * 二叉树直径
     *
     * @param root 根
     * @return int
     */
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return ans;
    }

    private int ans;

    private int dfs(TreeNode root) {
        if (root == null) {
            return -1;
        }
        int l = dfs(root.left) + 1;
        int r = dfs(root.right) + 1;
        // 两条链拼成路径
        ans = Math.max(ans, l + r);
        // 当前节点最长链
        return Math.max(l, r);
    }


    /**
     * 是否对称二叉树
     *
     * @param root 根
     * @return boolean
     */
    public boolean isSymmetric(TreeNode root) {
        return isSymmetricHelper(root.left, root.right);
    }

    private boolean isSymmetricHelper(TreeNode left, TreeNode right) {
        if (left == right) {
            return true;
        } else if (left != null && right != null) {
            if (left.val == right.val) {
                return isSymmetricHelper(left.left, right.right) && isSymmetricHelper(left.right, right.left);
            }
            return false;
        }
        return false;
    }

    /**
     * 对称翻转 二叉树
     *
     * @param root 根
     * @return {@link TreeNode}
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        //左右交换
        TreeNode right = root.right;
        root.right = root.left;
        root.left = right;
        if (root.left != null) {
            root.left = invertTree(root.left);
        }
        if (root.right != null) {
            root.right = invertTree(root.right);
        }

        return root;
    }


    /**
     * 最大深度
     *
     * @param root 根
     * @return int
     */
    public int maxDepth(TreeNode root) {
        return orderTree(root, 0);
    }

    private int orderTree(TreeNode root, int depth) {
        if (root == null) {
            return depth;
        }
        return Math.max(orderTree(root.left, depth + 1), orderTree(root.right, depth + 1));

    }


    /**
     * inorder遍历
     *
     * @param root 根
     * @return {@link List}<{@link Integer}>
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorderTree(root, res);

        return res;
    }


    private List<Integer> inorderTree(TreeNode root, List<Integer> ans) {
        if (root.left != null) {
            inorderTree(root.left, ans);
        }
        ans.add(root.val);
        if (root.right != null) {
            inorderTree(root.right, ans);
        }
        return ans;
    }
}